package number_1048;

import java.util.Arrays;

public class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> {
            return a.length() - b.length();
        });
        int[] dp = new int[words.length];
        dp[0] = 1;
        int res = 0;
        for (int i = 1; i < words.length; i++) {
            int maxValue = 1;
            for (int j = 0; j < i; j++) {
                if (words[i].length() - words[j].length() == 1) {
                    if (isStrChain(words[j], words[i])) {
                        maxValue = Math.max(maxValue, dp[j] + 1);
                    }
                }
            }
            dp[i] = maxValue;
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    private boolean isStrChain(String source, String target) {
        for (int i = 1; i <= source.length(); i++) {
            if (!target.contains(source.substring(i - 1, i))) {
                 return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        new Solution().longestStrChain(new String[]{"a","b","ba","bca","bda","bdca"});
    }
}
